package hot;

public class Num124 {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root) {
        if(root == null) return 0;

        int leftVal = Math.max(dfs(root.left),0);
        int rightVal = Math.max(dfs(root.right),0);
        int value = root.val + leftVal + rightVal;

        max = Math.max(max,value);
        return root.val + Math.max(leftVal,rightVal);
    }
}
